
/**
 * 
 * 
 * 找数字
 * 
 * 题目描述

给一个二维数组 nums，对于每一个元素 nums[i]，找出距离最近的且值相等的元素，

输出横纵坐标差值的绝对值之和，如果没有等值元素，则输出-1。

例如：

输入数组 nums 为

0 3 5 4 2
2 5 7 8 3
2 5 4 2 4
输出为：

-1 4 2 3 3
1 1 -1 -1 4
1 1 2 3 2
对于 nums[0][0] = 0，不存在相等的值。
对于 nums[0][1] = 3，存在一个相等的值，最近的坐标为 nums[1][4]，最小距离为 4。
对于 nums[0][2] = 5，存在两个相等的值，最近的坐标为 nums[1][1]，故最小距离为 2。
...
对于 nums[1][1] = 5，存在两个相等的值，最近的坐标为 nums[2][1]，故最小距离为1。
...
输入描述
输入第一行为二维数组的行

输入第二行为二维数组的列

输入的数字以空格隔开。

输出描述
数组形式返回所有坐标值。

备注
针对数组 nums[i][j]，满足 0 < i ≤ 100，0 < j ≤ 100
对于每个数字，最多存在 100 个与其相等的数字
用例
输入	3
5
0 3 5 4 2
2 5 7 8 3
2 5 4 2 4
输出	[[-1, 4, 2, 3, 3], [1, 1, -1, -1, 4], [1, 1, 2, 3, 2]]
说明	无
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
  * 

  题目解析
我的解题思路如下：

首先遍历输入的矩阵，将相同数字的位置整理到一起。

然后再遍历一次输入的矩阵，找到和遍历元素相同的其他数字（通过上一步统计结果快速找到），求距离，并保留最小的距离。

上面逻辑的算法复杂度为O(n*m*k)，其中n是输入矩阵行，m是输入矩阵列，k是每组相同数字的个数，可能会达到O(N^3)的时间复杂度。

有一个优化点就是，遍历元素 A 找其他相同数字 B 时计算的距离可以缓存，这样的话，当遍历元素B时找其他相同数字A时，就可以从缓存中读取已经计算好的距离了，而不是重新计算。但是这样会浪费较多空间。

实际机试时，可以看用例数量级来决定是否要做上面这个优化。如果数量级很小，则无需上面优化。如果数量级较大，则有优化的必要。

  */

public class 找数字 {
    
    public static void main(String[] args) {

        try{

            Scanner scanner = new Scanner(System.in);

            //二维数组 行 
            int m = scanner.nextInt();
            //二维数组 列
            int n = scanner.nextInt();

            int[][] martixArr = new int[m][n];
            //保存值 以及和值相同的 value 的坐标
            Map<Integer, List<int[]>> diffVauleMap = new HashMap<>();

            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){

                    int value = scanner.nextInt();
                    martixArr[i][j] = value;
                    //把相同的值的坐标写入 map
                    diffVauleMap.putIfAbsent(value, new ArrayList<int[]>());
                    diffVauleMap.get(value).add(new int[]{i, j});
                }
            }

            //遍历矩阵每一个元素，和其他相同数字的位置求距离，取最小距离
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){

                    int value = martixArr[i][j];
                    int minDis = Integer.MAX_VALUE;
                    
                    for (int[] pos : diffVauleMap.get(value)) {

                        int x = pos[0];
                        int y = pos[1];

                        if(x != i || y!=j){

                            minDis = Math.min(Math.abs(x -i)+Math.abs(y - j), minDis);

                        }

                    }

                    //赋值
                    martixArr[i][j] = (minDis == Integer.MAX_VALUE ? -1 : minDis);

                }
            }

            //输出
            Arrays.stream(martixArr).map(Arrays::toString).forEach(System.out::print);
            System.out.println("");


        }catch(Exception e){
            e.printStackTrace();
        }
    }
}
